COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	∂28-Sep-81  0641	Darden at SUMEX-AIM 	clippings and analogies 
C00006 00003	∂12-Oct-81  0705	Darden at SUMEX-AIM 	analogy.properties and relations  
C00012 00004	∂13-Oct-81  0726	Darden at SUMEX-AIM 	Tom D on analogy.properties and relations   
C00026 00005	∂17-Oct-81  0809	Darden at SUMEX-AIM 	Russ on properties and relations  
C00036 00006	∂TO DARDEN 17:57 13-Oct
C00048 00007	∂14-Oct-81  1948	Darden at SUMEX-AIM 	hello    
C00055 00008	∂17-Oct-81  0809	Darden at SUMEX-AIM 	analogy as shared abstraction
C00060 00009	∂18-Oct-81  1311	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Direct Matching vs. Abstraction    
C00071 00010	I remember noticing the number of
C00083 00011	∂27-Oct-81  0821	Darden at SUMEX-AIM 	analogy.implicitness    
C00088 00012	∂29-Oct-81  1614	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Notes on Mike's "shared abstractions"   
C00103 00013	∂31-Oct-81  0812	Darden at SUMEX-AIM 	more Russ on analogy    
C00115 00014	∂31-Oct-81  1227	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Analogy archive
C00117 00015	∂TO DARDEN@SUMEX 13:50 2-Nov
C00120 ENDMK
C⊗;
∂28-Sep-81  0641	Darden at SUMEX-AIM 	clippings and analogies 
To:   RDG at SU-AI
cc:   Darden at SUMEX-AIM

Hi, Russ.  Thanks for sending the clipping on Einstein.  We had John
Stachel down for a colloquium last spring.  I found the article quite 
interesting.  It is indeed an important question about how a famous person's
papers should be handled.  It's one reason to work wwith material about 
100 years old, so that personalities are less likely to be important.
   Thanks also for the analogy article. The idea of analogies being 
misleading is something I've been told by students from physics, who were 
given certain analogies, for e.g.space-time, and didn't realize what was 
positive vs. negative analogy until they worked through the math.
   I will indeed be interested in seeing your thesis proposal with 
analogy in the title.
  I'm sorry not to have been more communicative lately, but life is very hectic.
Full-time teaching always takes lots of time, even though my two classes this
fall are fun and small.  I'm teaching history of modern biology, and enjoying
looking again at Darwin's use of domestic selection as an analogy for natural
selection.  My discovery and analogy class unfortunately has only four students,
and only one of those has a computer science background. I'm also doing lots 
of committee work and I have charge of the Philosophy Department's word
processing system.  
   Adding to my business is the fact that my personal life these days takes 
me to Boston frequently on week-ends.
   How I long for the lesiurly days of my sabbatical at Stanford.
   Well, this isn't one of them and I have to get ready to go to class.
   You can send me your proposal on line.  I now have a nice little EPSON
printer here at home.
   Bye, Lindley
-------

∂12-Oct-81  0705	Darden at SUMEX-AIM 	analogy.properties and relations  
To:   Analogy seminar:

Hi, Folks.  I wonder if it is possible to revive our dormant analogy 
discussions.  I am teaching a course this semester at Maryland called
Discovery and Analogy in Science and going over much of the literature
that we covered so quickly at Stanford last year.  The press of teaching
and administrative duties has left me little time for electronic msgs,
but new ideas are occurring to me, and I would appreciate some feedback.
    We have just finished reading Mary Hesse's MODELS AND ANALOGIES and
Dedre Gentner's "Are Scientific Analogies Metaphors."  I am once again
puzzling over the differences between properties and relations.
(See analogy.hesse, msg of 27-May-81 for more details.)  Hesse argues 
for property matches of the following sort:
          Properties 	Properties of light

	echoes				reflection
	loudbrightness
	pitch				color
	detected by ear			detected by eye
	propagated in air		propagated in "ether"

The vertical relations are causal relations, hence they transfer, if
light is of the same type of causal system as sound.  The horizontal
relations are similarity relations.
     Gentner criticizes Hesse for looking for property matches rather
than structural, relational matches.  Gentner argues for the use of 
a "propositions network of nodes and predicates" as a representation
scheme.  AI question:  is this a semantic network?
   It seems to me that if Hesse's vertical relations must be causal,
then she is, in some sense, matching causal structures, but her 
more frame-like representation scheme obscures that fact.
   Here is my question for you all in AI:  how are relations represented
in units and slots?  The sound unit depicted above does not have an
explicit representation of the "vertical, causal relations".  Does the
causal interrelatedness of slots get represented by putting it into 
another slot, or some other way?  
   Gentner draws circles (nodes) and lines between circles (relations)
and boxes off of circles (properties) and then maps isomorphically to
an identical set of nodes and lines, though not necessarily identical
boxes (analogy as structural, but not property match).  Can all this 
be represented in units and slots? How?
   Mary Hesse thinks good scientific analogies have property matches
as well as relational matches; Gentner thinks good scientific analogies
have relational matches and few or no property matches.  At least some
of Hesse's examples of analogies involve relating two things that might
be members of the same inductive class; Gentner's are always sufficiently
dissimilar that they would never be so related.
  There is a deep metaphysical problem associated with properties vs.
relations: what are our basic ontological categories? Entities and 
properties or relations?  There is a very strong tendency in Western
thought to see substances (entities) as basic and to analyze relations
as dependent on substances interacting. Most of our discussion of analogy
thus far has focused on finding matches between properties of entities.
See discussions about protypes, exemplars etc. in various msgs
(e.g. STT on 27-Mar-81 and especially Tom D.19-Apr-81.) 
   Well, enough for now.  Any other thoughts about properties vs.
relations?
   Bye, Lindley
-------

∂13-Oct-81  0726	Darden at SUMEX-AIM 	Tom D on analogy.properties and relations   
To:   Analogy seminar:

Mail-from: ARPANET host SU-SCORE rcvd at 12-Oct-81 1502-PDT
Date: 12 Oct 1981 1423-PDT
From: Tom Dietterich <CSD.DIETTERICH at SU-SCORE>
Subject: Re: analogy.properties and relations
To: Darden at SUMEX-AIM
cc: CSD.DIETTERICH at SU-SCORE
In-Reply-To: Your message of 12-Oct-81 0701-PDT

Lindley,

It sounds to me, at least, that the debate over relations versus
features (aka properties) is not really very important.  For instance,
is COLOR a feature or a relation?  We might say that an apple is red
by writing RED(x) & APPLE(x), thus asserting that x has two features,
"redness" and "appleness".  Alternatively, we might say COLOR(x,RED),
thus saying that the COLOR relation holds between two entities, x and
RED.

In semantic networks, both techniques have been used.  Frame
representations, however, tend to employ the COLOR(x,RED)
representation.  That is, a frame is created for x, the frame has a
COLOR slot, and that slot is filled with the value RED.  

There are some relations that are difficult to represent as features.
For instance, to represent stacks of toy blocks such as the following:

 -----
|     |
|  A  |
|     |
 -----
|     |
|  B  |
|     |
 -----
|     |
|  C  |
|     |
 -----

AI people usually employ the representation

ONTOP(A, B) & ONTOP(B, C) & BLOCK(A) & BLOCK(B) & BLOCK(C).

It would be possible, however, if the structure was fairly static, to
employ a representation such as

BOTTOM-OF-STACK(C) & MIDDLE-OF-STACK(B) & TOP-OF-STACK(A) & 
    BLOCK(A) & BLOCK(B) & BLOCK(C).

However, this representation won't suffice if we need to describe
stacks of blocks that are arbitrarily large.  We can still get away
with it, though, if we can place an upper bound on the height of a
stack.  If we know that all stacks are 10 blocks or less, we can
create 10 properties and use only as many of them as we need.  Thus,
for a stack of only three blocks, we could use the representation

STACK1(C) & STACK2(B) & STACK3(A) & STACK4(NONE) & STACK5(NONE) & ...
    & STACK10(NONE)

The NONE entity says that there is no block in that position.  
In general, it is possible to convert ANY relational representation
into a feature-value representation IF the "size" of the relations can
be bounded in some way.  The feature-value representation is somehow
less natural, but it has the advantage of making certain inferences,
such as matching, much faster.  Thus, AI people tend to use
feature-value representations whenever they can get away with it.

Hence the popularity of frames.  When you use frames in which the slot
fillers are constants (rather than variables), then the frame is being
used like a vector of features, and you can compare the two frames
slot-for-slot.  The frames can be "superimposed" on one another, and
the comparisons made.  When variables are used as slot fillers, then
the slot starts behaving like a "relation", and matching becomes much
more complicated.  All occurences of the same variable must be found
and checked.

Virtually all frame-representations and semantic net representations
can be translated directly into first-order predicate calculus.  [the
exceptions to this statement involve extended types of inference, such
as non-monotonic reasoning.  Many AI researchers are working on
formalizing these non-standard inference techniques in predicate
calculus].  This is why most of us in these analogy discussions have
ignored the question of whether features or relations were being
matched and concentrated instead on the nature of the matching.

Given this introduction, let me try to answer your questions.
Unfortunately, I haven't read the relevant papers, so I may very well
be mistaken.  Here goes...

A "propositions network of nodes and predicates" sure sounds like a
semantic network to me.  That is, it sounds like she is using explicit
relations in her representation.  But, the preceding argument would
indicate that this is not particularly important.  What is important
is WHICH properties or relations are being matched?  I.e., the content
of the representation, rather than its form.  

If we use the following representation, in which the "vertical
relation" is represented as a single, grand relation, then, Gentner
would only match the symbol "superframe" in one case to the symbol
"superframe" in the other case:

Superframe(SOUND, echoes, loud, pitch, detected-by-ear,
   propagated-in-air) 
Superframe(LIGHT, reflects, bright, color, detected-by-eye,
   propagated-in-ether)

whereas, it appears from your description, that Hesse would match the
constants in the representation as well, by having some way of
determining that, for example, echoes and reflects were similar (for
example, she might have definitions of echoes and reflects in terms of
bouncing off of a physical surface, so that "bouncing off" and
"physical surface" could be matched to discover the similarity.)

This superframe representation trivializes Gentner's structural
match--there is virtually no structure to be matched.

An alternate representation, closer to the standard use of frames,
might be something like:

Frame(f1) &
  Slot(f1, s1) & Slot(f1, s2) & Slot(f1,s3) & slot(f1,s4) & slot(f1,s5)
  & Contents(s1, echoes) & Contents(s2, loud) & Contents(s3, pitch)
  & Contents(s4, detected-by-ear) & Contents(s5, propagated-in-air)


 Frame(f2) &
  Slot(f2, s1) & Slot(f2, s2) & Slot(f2,s3) & slot(f2,s4) & slot(f2,s5)
  & Contents(s1, reflects) & Contents(s2, brightness) & Contents(s3, color)
  & Contents(s4, detected-by-eye) & Contents(s5, propagated-in-ether)

Now, Gentner would match the symbols "Frame" and "Slot", and the
structural relationships among the various slots.  Such a match would
be completely structural, making NO use of the "CONTENTS" predicates.
I don't think such an approach is very plausible, though, because
there are 120 possible ways of doing the match (that is, s1 can be
matched to s2, s3, s4, or s5.)  However, if we appended the following
information to the above representation, then we might get something
that made sense:

   & Name(s1, bounce) & Name(s2, intensity) & Name(s3, frequency) 
   & Name(s4, detection) & Name(s5, medium)

Now, we can MATCH the SLOT NAMES as well, and now the match can only
be done in one way--the way that makes sense.  However, notice that we
have worked into our representation some of the important theoretical
terms for this area: intensity, frequency, detection, and medium.  How
plausible is it to suppose that these terms already exist in our
representation before we draw this analogy?

I don't like any of the approaches that I've outlined.  To me, it
seems that you need to work in a whole lot more knowledge about what
"echoes" and "loud" and "pitch" and "color" mean--perhaps in terms of
examples and sense experience.  All of these other representations are
too compact--they have boiled down all of the information into a very
simple structural form in which matching is either impossible or
trivial.  I need to think more about this, however.  I'll send another
message in a couple of weeks.  

Bottom line: the property versus relation argument is not central to
the analogy question: both properties and features need to be matched,
both are interchangable.  It is usually necessary to include relations
in any representation.  The important issue of WHICH features and
relations should be used in a representation, and hence, should be
matched, is a difficult one.  An important constraint on hypothesizing
representations is that each representation must be learnable from
some other representation.  We might call this the "evolutionary
adequacy" of a representation.

In answer to one of your other questions, YES, I think you can
represent both Gentner's and Hesse's approaches using units and slots,
just as you can use predicate calculus.  

I have a question.  What do you mean by "causal"?  I've been thinking
a lot about causality, and haven't gotten very far.  What do
philosophers thhink about causality?

I hope this made some sense.

--Tom

PS. Please forward this to everyone on the analogy list.
-------

-------

∂17-Oct-81  0809	Darden at SUMEX-AIM 	Russ on properties and relations  
To:   Analogy seminar:

Mail-from: ARPANET host SU-SCORE rcvd at 13-Oct-81 1404-PDT
Date: 13 Oct 1981 1405-PDT
From: Russell Greiner <CSD.GREINER at SU-SCORE>
Subject: Complexities of Analogies
To: darden at SUMEX-AIM
cc: rdg at SU-AI

Hi Lindley --

I had some thoughts indirectly related to the question you asked in
your recent letter.
They basically reflect my weariness of claims which are this general,
especially when they pertain to domains as "subjective" as analogizing.
Your message points out (what I feel is) one of the major problems of all
existing analogizing programs -- their heavy dependence on some particular
pre-defined formalism and on a specific, implicitly defined representation.

"... one man's relations are another man's properties ..."
Consider the clearly "structural" attribute that John likes Mary.
Using the binary "Likes" relation, one could assert that (Likes John Mary).  

[In units and slots, this could be represented by storing the value Mary
	in the Likes slot of the John unit -- pictorially shown as
  |-------------------|
  | John	      |
  |    Likes: (Mary)  |
  |-------------------|
	(I hope that comes out pretty on your terminal,)
	possibly augmented with a "back-pointer", as
  |-----------------------|
  | Mary		  |
  |   IsLikedBy: (John)   |
  |-----------------------|
]

Later on, that "another man" mentioned above will, on noting Mary's
likability and host of friends, define a unary relation, (now called a
property,) LikesMary.  The assertion is now the simple (LikesMary John).

Now consider the claim that the first of statements should be carried
across a good analogy, whereas the latter statement shouldn't;
in light of the fact that they both represent (semantically) the same thing.
(Note I'm NOT addressing the "pragmatics" here --
as I feel the "connotations of property-izing a relation" should play 
NO role, especially when dealing with an internal representation.)

Another example: should it really make a difference whether we say something
is red, (ie satisfies the unary Red predicate) or that it's color is Red 
(ie that that object participate in the ColorOf relation with Red)?
Is "IsaPerson" more natural than "Isa"?
Or consider the meta-relations, Name vs NamedLindley... etc, etc, etc.

The standard retort here is that one encoding is more natural,
and the other but a contrived aberration.  Well, maybe... 
But then who should decide this issue?   While there may be some
general "truths", these can (at best) only be in the form of 
psychological data -- and I do not feel the criteria for specifying and
defining an analogy should be in terms of such observations...

This may be what makes analogizing both interesting and elusive.  
When seeking an analogy, any individual will utilize his particular 
"encoding system" in deciding what is significant.
This particular example leads to a more general claim:
that any predefined specification will be subject to this same criticism
of limited applicability, and/or general fuzziness.
Ie you would find it equally trivial to critize/caricature any particular
scheme I might come, as it would necessarily be based on my particular
prejudices.

This is why I am making a effort to divorce the process of analogizing
from the particular representation used. 
In my work, I intend to start with something as "neutral" as possible
-- like Predicate Calculus.
The user will be able to enter his particular analogizing heuristics in terms
of this "unbiased" description; these are then incorporated into the
actual "analogizing module".  
It is these subjective, user-dependent rules which constitute the criteria 
for evaluating any given analogy, or for comparing proposed analogies --
not some sacred set of specifications which had been giveth unto it.
(Of course, the user is free to use someone else's particular criteria,
sparing him the arduous overhead task of entering such data.  The point
here is that he is also permitted to change these rules if he wishes,
or to enter his own biases.)
Anyway, I say quite a bit about this in my thesis proposal; which, who knows,
may actually be released of these days.

One final point: I am NOT saying that I disagree totally with Gentner, et al.
In fact, it seems obvious that the value of finding a pair of corresponding
N-ary predicates should vary monotonically with N.
I do intend to include this heuristic in my starting collection of
suggested rules.  (Indeed, much of Carbonell's
"invariance hierarchy" will be used in this same way -- as a set of particular,
defeatable suggestions.
They depend far too much on the particular decomposition of "facts
about the world" into attributes to earn the status of iron-clad,
inviolatable rules.)

Conclusion:
The analogizing process seems much too complex to be so tied to the
particular representation used!
It is this (fallacious) attitude that has led people
(including me at times) to the belief that one can form analogies
using a purely syntactic mechanism -- eg by simply matching some predefined set
of features, using some weak (ie unspecialized) method.

I certainly hope that there is something more semantic to Analogies than that.

Russ
-------
Although I got a second msg from Russ, following this one, saying that he 
realized that Tom had said some of these same things about properties and 
relations, I decided to go ahead and send Russ's msg around.  I wonder what
it means to say that different people have different representations for
analogies?  I hadn't considered that theprocess of forming analogies might
be strongly dependent on individual psychological variables.
Lindley
-------

∂TO DARDEN 17:57 13-Oct
Oops
I just noticed that Tom already sent out a note,
whose contents had a non-trivial intersection with mine.
Sorry to force you to read through that rhetoric twice.

Also, feel free to circulate any (possibly trivial) subset of my 
message which you think might be relevant.

By the way, how are you these days?  and things there in general?  
(I realized my last letter was a little impersonal, if not downright
hostile.  Sorry about that...)

I've spent the last few weeks trying desperately to answer several
groups of people's "well, where is it?" questions.  (Each referring to
a different "it"...)   Like the rest of us, I had incredibly
overcommitted myself.  However, I did manage to reach a plateau (or
conclusion) for two of the four main projects (viz. time consuming
tasks for the student orientation committee, and some RLL-related stuff for 
ISI,) leaving me with only RLL stuff for Rand and (finally) a thesis proposal
still to do.  Both are well along - at the "light at the end of the tunnel"
phase.

Anyway, I plan to commit much of this week to polishing (well,
after generating) that proposal -- hopefully bringing it to a point that 
I can send it out for comments, (further burdening people like you.)
By the way, I wanted to thank you again for your offers of advice --
it really is nice to have the backing and criticisms from people with
both your knowledge and enthusiasm.
It will be quite useful to find just how naive my approach really is...

Caio,
	Russ
∂14-Oct-81  1948	Darden at SUMEX-AIM 	hello    
To:   rdg at SU-AI
cc:   Darden at SUMEX-AIM

Hi, Russ.  I didn't mind reading the relations-property stuff you sent,
even though it was quite similar to Tom's response.  Obviously you all are 
thinking along the same lines and it is useful for me to hear.  I will be 
very interested to see how you allow analogies to be formulated without
having to be committed to a prior representation scheme.
  My time is filled with many things that aren't much fun at the moment:
grading history of biology papers, doing committee work for the graduate 
program, etc.  I would much rather have time to learn more AI, work on
a paper on analogical reasoning, and finish my work on the history of 
genetics.  I've been writing grant proposals to have next year in Boston
but money for philosophy of science is not easy to get.  I would
like to do a book on theory construction, with the theory of the gene as 
the major case study.
   Did you see Doug Hofstader's article on analogy in the September 
SCIENTIFIC AMERICAN?  I thought it was rather shallow, but students in
my discovery and analogy class had fun with the Nancy Reagan
is to the Us as (blank) is to Britain.  We've been playing with
the idea that people can recognize analogies prior to being able tosay
explicitly what the analogous relations are.  I have 
no idea what implication that has for AI analogy formation.
  I've enjoyed the various wire service items you have sent.  Keep in 
touch and good luck with your proposal.  It is an important topic.
  Bye, Lindley
-------

∂TO DARDEN@SUMEX  15:19 16-Oct
Misc remarks
Lindley -

Yes, I did indeed read thru Doug's article, months ago; and then
offered to circulate it on the analogy bulletin board.
He decided against such "advance publicity" --
I was really disappointed to find he had no interest in getting
any feedback.
Anyway, the article did indeed touch on some of the problems with analogy:
in particular, that whole issue of how to determine the appropriate
context on which to base the comparison.
[The term "context" is based on some recent musing of mine -- it's designed
to subsume things like perspective, recent (linguistic) focus,
the speaker's model of his audience, and everything else.  
One of my goals is to structure
this "general catch-all" into some well defined, and useful, entity.]

(In case neither the article nor Steve ever mentioned it:)
Two of his students - Gray [no, that's NOT a typo] and Marsha - are working
on a program, cutely (cutesy-ly?) titled "SeekWhence".  
It's designed to generate analogies, and other sorts of high level mumble
jumble.  An important part will deal with self-inspection -- designed
to notice when if ever some internal state is repeated. 

<Compare this to Mike's position that two models are analogies if they 
share a partial theory (which he calls an "abstraction"). 
Imagine, for argument's sake, that we each time we experience some
phenomena we internally store something like a theory of that event.
This would mean that we would store this same "neural pattern" (or whatever)
each time we had an analogous "experience".
Hence the ability to perceive such "coincidences" would be a powerful
analogizing tool.

Example: When contemplating the "leadership" organization of a company,
imagine I store (something isomorphic to) a theory of hierarchies.
I would also store a similar structure when thinking about biological trees.
[This theory of hierarchies provides the common abstract which makes
businesses and trees analogous (using Mike's definition).]
Notice this means I would be in the same internal "configuration" each
time I encountered any instance of a hierarchy.  
So any time I noticed that my internal structure is in this 
"storing a hierarchy configuration", (for example, when someone explains
the boss-of relation of a corporate structure,)
I should feel I'm confronting something analogous to the branchiness
of biological trees,
as I was in this same configuration when incorporating that.
....
Yes, that was a lot of handwaving.  Perhaps its was merely an attempt
to force two intrinsically dissimilar ideas into an analogy...
Of course people are good at that.
End of digression, from digression.>

Any of this make sense?

That's all for now.  Back to thesising.
	Russ

∂17-Oct-81  0809	Darden at SUMEX-AIM 	analogy as shared abstraction
To:   Analogy seminar:

Hi, Folks.  I got a brief msg from Russ about Mike G's idea of analogy
as a shared abstraction.  Russ suggests that when people perceive new
things, such as the hierarchical organization of a company, they may
store an abstraction that will then get matched to other things with
a similar structure, e.g. a biological tree. 
  Ihavebeen thinking a lot lately about analogies as shared abstractions
vs. analogies as direct mappings between particulars.  There seem to 
be advantages and disadvantages to both analyses.  If one has astractions,
then the relations among analogues is identity, a much easier relations
to deal with than vague "similarity." Also, we might hope to be able to
get a typology of abstractions and use them for whatever purposes we use 
analogies. In my cases, that would mean a typology of theories that could
be used when we come to construct a new theory.  On the side of direct 
mapping, however, is the ability to go back and make use of additional 
properties of the analogue that were not exploited at the outset and that
would not (or might not)have been included in an abstraction.  Mary Hesse
argues that the extendability of theories in the face of anomalies depends
on having additional neutral analogy available to exploit.  I have found
(actually a student of mine found) an excellent example of this in Darwin's
use of domestic selection as an analogy for natural selection.  After the
theory was already constructed, Darwin faced the problem of how neuter
insects could be perpetuated since they didn't reproduce.  He went back
to the domestic slection case and said that even though we eat, e.g. a pea,
we can select the "stock" from which the good tasting peas come to plant.
So, he proposed a kind of (what we now call) "kin selection" to explian
why that stock of the neuter bees would pass on the neuter trait. The
information about choosing the stock was not part of the original match
and would not have been included in an abstraction.
   One suggestion for how to build an analogy system would beto use
both shared abstractions and direct mappings: use an abstract type is
it solves a problem butkeep around the detail instances with additional
properties to be used if the abstractions fails to supply what is needed.
Thus, one would have an abstract selection model, consisting of variants,
a means of choosing among variants, and the differential reproduction of 
the chosen ones.  Domestic selection and natural selection would be 
instantiations of this model.  But when the problem of neuter insects 
arises, additional details from domestic selection are examined, since
the abtract model does not aid in the solution.
   Any comments?
   Bye, Lindley
-------

∂18-Oct-81  1311	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Direct Matching vs. Abstraction    
To: Analogy-seminar: ;

Lindley,

Your message about stored abstractions vs. direct mappings was very
interesting, and I thought I'd respond by trying to synthesize the two
views and share a few ideas about analogy that have occurred to me
recently.

Let me restate the two views in slightly exaggerated form:

DIRECT MAPPING:  An analogy is a direct mapping between particulars A
and B.  (A and B could be objects, situations, events, configurations,
devices, mechanisms, etc...., we will call them objects from now on.)
It specifies how A and B are the same (POSITIVE ANALOGY) and how they
are different (NEGATIVE ANALOGY), and perhaps even the ways in which
it is not known how they are the same or different (NEUTRAL ANALOGY).
I doubt that NEUTRAL ANALOGY can be explicitly represented, since a
person (or a program) cannot possibly know everything about an
object--and all of the unknown features of the object are neutral
analogy.  When the analogy is set up, the person will pursue it long
enough to determine that there is a positive analogy (and thus a basis
for the analogy) and to use the analogy to map some of the neutral
analogy across.  Everything else that is unknown is neutral, and can
be used at some later time to extend the analogy.

SHARED ABSTRACTION:  An analogy is a mapping between a shared
abstraction S and two particulars A and B.  A and B are both
recognized as being instances of S.  The shared abstraction tells how
A and B are the same.

There are two issues that arise from these definitions: (a) How do we
find analogies? and (b) What do we use them for?  


FINDING ANALOGIES

The shared abstraction position says that we find analogies by
recognizing instances of our pre-existing shared abstraction S.  This
is very nice for mature systems, but it ignores the question of where
S comes from (i.e., it is evolutionarily inadequate).

The direct mapping position says that there is some super mapping
process that is able to compare objects and decide when (and how) two
objects are similar.  This is known to be computationally expensive,
especially for "large" objects (i.e., with many subparts).


USING ANALOGIES

The direct mapping view says that analogies are used to hypothesize
ways in which A and B are similar.  The neutral analogy of A and B is
hypothesized to be positive.  This is a very attractive idea, because
it provides a generator of new ideas:  you just think of everything
that you know about A, and hypothesize that it is true of B (and vice
versa).  If your knowledge of A is unbounded, then so is your
hypothesis generator.

The shared abstraction view presumably could support the same kind of
"transfer of properties" as the direct mapping view, but there is no
supporting framework for keeping track of the negative analogy.  This
is not a fatal flaw--such a framework could be provided fairly easily.

Mike Genesereth has pointed out another value of having a shared
abstraction:  you can attach an efficient simulation structure
(computational partial model) to the abstraction and use it to improve
the efficiency of representation and inference.  [I think this is the
main point of his Metaphors and Models paper in AAAI, isn't it?]  This
is one advantage of having an explicit abstraction structure in your
representation. 


COMMENTS

I think the two views can be combined as follows.

Start with the direct mapping approach.  When A and B are found to be
similar, create a shared abstraction and look for an efficient
computational model of that abstraction.  In other words, when you
discover that "maple tree" and "IBM organizational structure" are
similar, look for ways in which the shared abstraction, "hierarchy",
is similar to something in a computer, and use that similarity to
build a computational model for the abstraction.

When new objects come in, first look for similarity with existing
abstractions.  If none are found, then fall back on the weaker direct
mapping approach.

Employ the POSITIVE/NEGATIVE/NEUTRAL idea to generate new hypotheses
and attempt to extend analogies.

Summary: an abstraction is a "cached analogy"


OTHER POSSIBILITIES:

Another use of analogies is to represent partial knowledge.  It is
possible that a system could set up an analogy that was believed to be
true, but that had almost NO POSITIVE ANALOGY.  This is just another
way of looking at analogies that stresses the role of the NEUTRAL
analogy.  In learning and theory formation, it is important to
represent everything you know, even when it is very weak knowledge.
Existing systems, such as Meta-DENDRAL, usually do this by
enumeration:  If there are several possibilities for the right answer,
we typically list them all.  Unfortunately this requires a generator
of all of the possibilities (and an explicit representation for them).
Analogies may provide an implicit representation for partial
knowledge.  We may not know exact what the answer, A, is, but we know
that it is like B (and also like C), etc.  This is just a vague idea
that needs a lot more work.

The problem of finding analogies is very difficult.  It may be that we
can make use of some existing abstractions in order to help guide the
matching process.  We need to develop a large body of heuristics that
can guide the search for analogies.   Winston proposed "causality".
Carbonell elaborated on this with his idea of an "invariance
hierarchy".  Dave Smith has suggested context-dependent heuristics
that might suggest certain dimensions along which the two objects
should be compared.  One might imagine a "fingerprint" heuristic:
take some unusual property of A and go looking through your knowledge
base for things sharing that same unusual property.   Anyway, there is
a lot of work to be done in this area.

Actually, the shared abstraction vs. direct mapping argument is
related to the larger question of the role of memory organization vs.
inference.  Are there ways of organizing memory that making it easy to
find analogies?  Evidently, people have many important associative
links in their brains.  Words, for instance, seem to be cataloged by
sounds (vowel sounds, initial consonant, etc.).  Perhaps there is an
organizational skeleton that will simplify the matching process.

Well, that's all for now.

--Tom
-------

I remember noticing the number of
I keep finding analogies about analogies -- like writers writing about
writers, or songs about singers, ...
∂27-Oct-81  0821	Darden at SUMEX-AIM 	analogy.implicitness    
To:   Analogy seminar:

     This is a reply to Tom's message of 18 October 1981 on the topic
of direct matching vs. shared abstraction as analyses of analogical
reasoning.
     I agree with much of what Tom says about the advantages and
disadvantages of the two approaches. The most interesting comment in his 
msg if this: "Analogies may provide an implicit representation for partial
knowledge." I have been thinking a lot lately about humans' abilities
to see that A is like B, without being able to say explicitly what the
similarity relation is; further analysis will often enable a person to
say what the relation is. Thus, the first step, by humans, in finding
analogies may be some implicit recognition of similarity. I've had fun
with my students asking them about Doug Hofstader's analogy (in the 
September 81 SCIENTIFIC AMERICAN) Nancy Reagan : US :: ? :Great Britain.
I usually get immediate responses and later the students analyze what
the relevant comparisons were that they were using (sex, position).
     But I have no idea how we could build a system
that would recognize implicit similarities or differences
(it sounds impossible) or make use of them.  It seems to me we have to
figure out what it is that humans are doing (e.g. direct mapping vs.
finding shared abstractions), even if humans aren't consciously aware 
of the process. If we can figure it out, or construct something that 
will function in the same way even without knowing whether it is the way
humans do it, then we may be able to build a system to do it.
     A few other comments about other parts of Tom's msg:
In discussing the use of neutral analogy to generate new ideas Tom says"
"you just think of everything that you know about A, and hyothesize that it
is true of B (and vice versa). " However, you would like to have some way
of telling ahead of time which aspects of the neutral analogy will be 
likely to be positive and which negative. To solve this problem, Mary Hesse
and Winston have instroduced the idea that there should be causal relations
among the already established poistive analogy and the aspects of the 
neutral analogy that you transfer.  Gentner wants the relations that are
mapped over to be part of a "mutually constraining system" (whatever that
is).  I think causal interrelatedness is probably too strong: few
analogies are going to provide tight causal systems. But we do need
heuristics (probably coming from the problem-context) as to what kind of 
properties and relations we expect to map over, e.g. if we are looking
for analogies to the structure of the atom, we will map structrual 
properties. This topic needs a lot more thought.
     I don't understand Mike G's point that Tom discusses: "you can 
attach an efficient simulation structure (computational
partial model)[what is this?] to the abstraction and use it to
improve the efficiency of representation and inference." [How?]
Tom, can you or Mike explain this to me?
     Well, enough for now.
    Bye, Lindley

-------

∂29-Oct-81  1614	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Notes on Mike's "shared abstractions"   
To: Analogy-seminar: ;

Lindley,

This is a response to your request for a clarification of Mike's
"abstraction" idea.  Since he is so busy these days, I thought I would
respond b∨ attempting to set forth his position and then criticize it.
I hope I'm dong him justice.  My main source is his AAAI paper
(Metaphors and Models) and my own conversations with him.

Mike's main assertion is that there exist (ideally?, or in the makeup
of the human brain?) certain computational structures, such as trees,
that can be represented compactly and reasoned about efficiently.
He calls these computational structures SIMULATION STRUCTURES (after
Weyhrauch).  He goes on to make two major claims:

Claim 1.  Good simulation structures are "potential wells"--sources of
many good analogies.  They capture some common structure that
frequently appears in the real world.

Claim 2.  The process of finding an analogy is the process of
discovering (or recognizing an instance of) one of these structures.
Theory formation is also related to finding one of these structures
(He is very vague on this).

First, let's look at an example of a simulation structure and how
Mike's program actually uses them.  Then we can take up these claims.

Mike's favorite example is a tree or hierarchy.  A tree can be
represented compactly as a LISP list structure.  Imagine a
formalization in logic of the organizational chart of a corporation.
The formalization would include axioms like

supervises(Genesereth, Smith)
supervises(Feigenbaum, Genesereth)
supervises(Genesereth, Paulson)
... 

along with axioms such as

(A x,y) supervises(x,y) -> boss(x,y)
(A x,y,z) boss(x,y) & boss(y,z) -> boss(x,z).

In LISP, we can implement the boss predicate as the CDR pointer in a
linked list:

(Feigenbaum  (Genesereth  (Smith
			   Paulson))
	     (Buchanan (...))
             (Lenat (...)))

and we can implement the transitivity axiom by an inheritance
algorithm: to test if boss(x,y) is true, start with the y and search
upward through the tree (i.e., left-ward in the linked list) for x.
This computational implementation thus allows very efficient deduction
of the fact "boss(Feigenbaum, Paulson)".  We start at Paulson and
search leftward for Feigenbaum.

In terms of formal logic, the simulation structure is a partial model
(in the Tarskian sense) of the axioms.  Some inference can be done in
the model and then mapped back into the axiom system as necessary.  As
Russ points out, Mike calls the axiom system an ABSTRACTION.

Mike's program, ANALOG, looks for situations in which it can use the
tree simulation structure IN PLACE OF the axiom system.  He sees two
basic advantages:  more compact representation and more rapid
inference.  The tree representation is more compact than a set of
axioms, since only one memory location is needed to store each "fact"
of the form "supervises(x,y)".  And as we have seen, inference is
quite fast as well.  Mike does point out that there are disadvantages
associated with using simulation structures.  Facts must converted
into a canonical form in order to be stored.  Partial knowledge is
hard to represent:  if we don't know who supervises Dietterich, for
example, we can't put him into the list.

When Mike's program finds a situation in which the tree structure can
be used, it converts all (or as many as it can) of the facts that were
stored in a uniform logical representation into the tree structure
representation.  

Mike's program thus has two tasks:  (1) to recognize the applicability
of one of its simulation structures, and (2) to actually apply the
simulation structure.  The problem of recognizing the applicability of
a simulation structure is basically the problem of finding an analogy
between the situation and the simulation structure.  Mike doesn't say,
in his paper, exactly how this is done.  He says "there is a knowledge
base describing some of the best data representations and algorithms
known to computer science."  This knowledge base is used to select one
of the existing simulation structures for use in representation.

To actually apply the simulation structure, Mike points out the need
for a procedure for mapping each logical assertion into its
corresponding assertion about the simulation structure.  This is
basically the "analogy map" telling how the two things correspond.  An
interesting thing about this map is that ALL of the simulation
structure must map to SOME of the logical axiomatization.  This is an
easier matching problem than the problem of finding a partial match
between two complex entities.  This match is partial for the logical
axioms but total for the simulation structure.

Now that we have seen what Mike's program does, we can summarize the
main points:  (1) There are things called simulation structures that
have particularly nice properties.  (2) He has built a system that can
recognize when these structures can be applied and that applies them
to improve the representational and inferential efficiency of his
system. 

Now we turn to his claims about the larger issues of analogy.  First,
let's take up the question of the existence of these simulation
structures.  Are there only a few good simulation structures around?
Mike lists hierarchies, grids, partial orders, rings, groups, and
monoids, as examples.  Computer scientists study a variety of special
graph structures such as bipartite graphs, planar graphs, and complete
graphs.  Mike also mentions the trick of using a bit-string to
represent a set, by assigning one bit to each possible element of the
set.  Mike lists a set of considerations that bear on the problem of
inventing new simulation structures.  One approach, for example, is to
choose a particular level of analysis and represent each individual by
a single structure in the machine.  Thus, with sets, we represent each
potential element in the set by a single bit in the machine.  With
trees, we represent each person in the organization as a single node
in the tree.  Similarly, it may be important to choose a single
relation to serve as the backbone of the simulation structure and
deduce the other relations as necessary.  Thus, in the tree, we chose
the "supervises" relation to organize the tree, and computed the "boss"
relation as necessary.

From the above discussion, we can conclude that there are, indeed,
many good simulation structures around, and that there are even some
principles for designing new ones.

Now, let's take up claims 1 and 2--namely, that simulation structures
capture some pattern that frequently occurs in the world, and that
finding an analogy is the problem of finding a simulation structure.

Claim 1 is, in a sense, self-fulfulling.  A good simulation structure
is one that is useful.  A simulation structure is useful if it appears
often in the world.  But, this isn't quite the full story.  Basically,
Mike is asserting that if something is efficient computationally, then
it should be useful for representation.  He even goes so far as to
suggest that the computer should "bend" reality to make it "fit" the
simulation structure.  This is equivalent to asserting that the
computational structure of our brains mirrors, in some sense, the
structure of the world.  He admits that this is implausible for
current computers, but asserts--rather weakly--that VLSI will change
all that by providing new computational structures.

It is an interesting assertion that the structure of our minds
influences the way we perceive the world.  If claim 1 is true, then
computers will probably perceive and organize the world (i.e.,
discover abstractions and analogies) differently than people.
Still, I have my doubts about claim 1.

Claim 2 says that, SINCE simulation structures capture regularities in
the world, we can find analogies by either looking for instances of
existing simulation structures or else inventing new simulation
structures.  This certainly makes sense.  The only issue is whether or
not there are any other ways of finding analogies.  Mike hasn't really
addressed this question.  It seems to me that there are
analogies--such as the analogy underlying the "man is a wolf" style
of metaphor--for which there is no corresponding simulation structure
on current computers.  Mike can counter, however, with the argument
that perhaps there is such a simple structure in the human mind.
Still, I think analogies are too common and varied to assume that some
efficient computational structure underlies each one of them.

Conclusion:  

Mike's idea of efficient simulation structures is nice, and it gives
another heuristic for analogy programs:  try your known efficient
simulation structures before you go looking for complex partial
matches.  However, I don't think simulation structures provide a
complete account of analogies or theory formation.

--Tom
-------

∂31-Oct-81  0812	Darden at SUMEX-AIM 	more Russ on analogy    
To:   Analogy seminar:

Mail-from: ARPANET host SU-AI rcvd at 28-Oct-81 1434-PST
Date: 28 Oct 1981 1431-PST
From: Russell Greiner <RDG at SU-AI>
Subject: Third Def'n of Analogy, and other meaningless dribble 
To:   darden at SUMEX-AIM, TGD at SU-AI    

Lindley, Tom -

Actually, I was defining analogy in (yet a) third sense:
Two "objects" are analogous if they both satisfy the same (partial) theory.
Hence TGD and RDG are both models of the "theory of Stanford CS grad students".
[Ie both (of us) satisfy the single statement

<1>	(Exist (S) ((Student S) & (Location S Stanford)
				& (Dept S CS) & (Level S Grad))).]

A more complicated example might involve something like the theory of groups,
or the theory of a hierarchy.
(Note that both a corporate hierarchy and a biological tree satisfy that theory.)

Mike (ab)used the term "Abstraction" to refer to that partial theory...
I find it very easy to abandon that confusing term in favor of the
more accurate and less misleading phrase, "partial theory".

In some cases one can easily concoct the Abstraction from a partial theory --
as the minimal model of that set of statements.
[I'm not sure this is always possible, or if that minimal model is well defined.
Any logicians out there?]
In the case of <1>, one could simply
define an intensional object which has just the properties required of
that existentially quantified variable x.
Hence the Abstraction for RDG and TGD would be that
theorized standard "Stanford CS grad student", hereby labeled TypicalS-CS-GS.
Note nothing is known about this entity beyond these 4 characteristics.

But what about deductions which follow, you may ask?  Eg as 

<2>	(All (x) (Student x) => (Person x)),

can't we conclude (Person TypicalS-CS-GS)?  
The answer, of course, depends on where statement <2> came from.
Answers like "obvious common sense" or "from the inheritance hierarchy"
are not allowed.  Rather, if one wants to make assertions like <2>,
he may; provided he has entered such rules explicitly.
As none of these facts are hidden, it is straightforward to determine
just what the system "knows" about some object, and from this, the
type of analogies it will be able to generate.
(This is what I meant in my last message about an unbiased "neutral" starting
state.)

Anyway, there are some advantages of this partial theory approach over the
abstraction one.
The first difference (which I consider an advantage, but others may disagree)
is that it forces even "obvious" facts to be entered explicitly.
(Let me contrast this with (my cariacture of) the Shank-ian view
that the original programmer should simply build every possible 
common-sense idea/rule/theme imaginable into the program itself.
From here that program has the trivial "syntactic" task of matching, ...
or whatever to achieve human performance.  
The problem with this approach -- the reason I cannot imagine it actually
working -- is with the (ridiculous) assumption that there can be
some universally-accepted, unbiased initial stash.  
I question whether there even is such an all-encompassing set of facts,
and even more whether any coder could possibly envision it.
As that set is so incredibly ill-defined, and subjective,
it seems a real loss to encode this, inalterably and implicitly, in a
program.  End of beating-up-on-straw-man.)

As a second possible advantage, note there is no need to create that
usually artificial abstraction entity.
One can, instead, deal exclusively with its description 
(in term of neutral predicate calculus statements, or whatever).

Another plus answers Lindley's question posed in her most recent message:
[The question about "an efficient simulation structure (computational
partial model)"]
One may store a set of inference procedures (and associated data structures)
with a given theory.  This simulation structure will, by design,
apply to any model which satisfies that particular theory.
For example, one may have an efficient mechanism for dealing with
retrievals from a hierarchy.  This set of procedures could be applied 
every time we find something which fits into this framework.
(See MRG's recent paper for details...)

By the way, I think Lakoff & Johnson, in their "Metaphors We Live By",
are claiming that people too possess and use certain specific
(efficient) mechanisms for a variety of computations.
Further, (I infer that he claims that) this ability developed for use in
one particular domain, but was
later applied to some other "analogous" domain,
that is, to another model which satisfies the same theory.
[Let me tone down my claim:  what follows is not obviously inconsistent with
their claims.  See their article in "Cognitive Science", Vol 4, Number 2 
[April-June 1980], pp 195-208.]

For example, people often refer to their emotional state in terms of
up versus down -- as in "he's feeling low today",or  "she's flying high today".
Perhaps people have some special purpose "hardware" for handling
linear-orderings in general.
As (one of) its primary uses is to describe the spatial up to down continuum,
our vocabulary, for this theory, has been based on this set of spatial terms.
Now along comes some other phenomena which also deals with a linear ordering,
as say the happy-to-sad (pseudo)continuum.
Why not use this linear-ordering hardware for doing things like, say, comparisons
(using its transitivity)?  For that matter, why not for communicating?
It is this second use of that hardware that prompts us to use spatial terms
for describing emotions.

Note this will work in any situation where the same theory which applies
to one domain happened to apply to another.
Here any example of a linear ordering will do -- such as quantity
("Number of books printed this year is up") or goodness 
("The quality of life is high these days").
Of course there is nothing special about linear ordering -- their
Cognitive Science atricle contains a wealth of these 
(oops, quantity as precious possession...).

End of digression.  Of course I totally ignored the issue of indexing:
just how does one locate the relevant theory for a given new model?
There is no a priori reason to think this process would be any easier
that finding an apt abstraction, or forming a new mapping.
Any ideas?

Anyway, the efficient computational partial model would be the algorithms people
have for dealing with linear orderings, or whatever.  For example, one
could represent any linear ordering as a straightline. In this model GreaterThan
would be trivial to compute:  it would be true if the first value was to
the left of the second.  (For comparison, consider the model which represented
each term with its english spelling.  Here ">" is incredibly indirect, and
hence expensive.)

-----
That's all for now.  As usual, if you think any of it makes sense, please
forward it along to the rest of analogy mailing list.

Russ


-------

∂31-Oct-81  1227	Tom Dietterich <CSD.DIETTERICH at SU-SCORE> 	Analogy archive
To: Analogy-seminar: ;

For the past few months, I have been maintaining a combined archive of
all of the messages from the analogy seminar on the file
[score]<csd.hpp-utilities>analogy.msgs.  About once a month, I move
recent analogy messages into this file and delete old ones.  Before I
delete old messages, I archive the whole file at SUMEX, so all of our
messages are saved for posterity.  I don't know if anyone else out
there is maintaining an analogy archive, but I thought I'd let you all
know so that if you like, you can delete your copies of analogy
messages after you have read them, and refer to my archive file for
old messages.  This is particularly relevant since we (especially I)
have been very long-winded of late, and those messages sure take up a
lot of space!!  If you need to see some REALLY old messages, let me
know, and I'll restore them for you.

--Tom
-------

∂TO DARDEN@SUMEX 13:50 2-Nov
Recent NOVA
Lindley -
	Did you see the latest NOVA show?  
It apparently dealt with flaws (real and imagined) in Darwin's ideas.
I unfortunately missed all but the last few minutes of it last night;
I do intend to see it in its entirity when next it repeats.

(Transcripts are available for this show, if you're interested.)

Russ

∂05-Nov-81  0806	Darden at SUMEX-AIM 	Re: Recent NOVA    
To:   RDG at SU-AI
cc:   Darden at SUMEX-AIM, STT at SU-AI

In response to your message sent 02 Nov 1981 1350-PST

Yes, I saw the recent NOVA entitles "Did Darwin getit Wrong?" I thought
it was intellectually muddled.  It mixed up creationist challenges to
evolution ("decent with modification) with scientific challenges to
Darwin's version of the theory of natural selection.  This confusion 
of the ambiguous "theory of evolution", i.e. descent with modification
and the mechanism to explain such species change, is rampant today.
Although some of the people on the show made the distinction, it was
NOT made clear to the average viewer.  The views of Eldridge and Gould
on punctuated equilibria (i.e. long periods of stasis then rapid 
speciation) present an important challenge to the gradualism that 
Darwin postulated; but they do not deny that natural selection is an 
imporant agent in selecting adapted forms.  The relations between Darwin's 
views and the newer scientific mechanisms were not made clear in the show.
Nonetheless, it is worth seeing to hear the interesting cases from the 
paleontological record.
   Bye, Lindley
-------